; SICP, 2.66
; Implement the lookup procedure for the case where the set of records is
; structured as a binary tree, ordered by the numerical values of the keys.

; Return the found record or nil.
; If the key is string instead of number, string=?, string<? and string>?
; can be used to compare keys.

(define nil '())

(define (make-tree entry left right)
  (list entry left right))
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))

; Suppose the key of a record is the car of it.
(define key car)

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
    nil
    (let*
      ((this-record (entry set-of-records))
       (this-record-key (key this-record)))
      (cond ((= given-key this-record-key) this-record)
            ((< given-key this-record-key)
             (lookup given-key (left-branch set-of-records)))
            ((> given-key this-record-key)
             (lookup given-key (right-branch set-of-records)))))))
; Test
(let
  ((records (make-tree '(5 five)
                       (make-tree '(3 three) nil nil)
                       (make-tree '(7 seven)
                                  (make-tree '(6 six) nil nil)
                                  (make-tree '(9 nine) nil nil)))))
  (display (lookup 3 records)))

